package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * https://leetcode.com/problems/insert-delete-getrandom-o1/
 * @author tzp
 * @since 2020/9/29
 */
public class LC380 implements ArrayProblem {

    public static class RandomizedSet {

        HashMap<Integer, Integer> map;
        ArrayList<Integer> array;
        Random randomor;

        /**
         * Initialize your data structure here.
         */
        public RandomizedSet() {
            map = new HashMap<>(256);
            array = new ArrayList<>(256);
            randomor = new Random();
        }

        /**
         * Inserts a value to the set. Returns true if the set did not already contain the specified element.
         */
        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            }
            int size = array.size();
            map.put(val, size);
            array.add(val);
            return true;
        }

        /**
         * Removes a value from the set. Returns true if the set contained the specified element.
         */
        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            int pos = map.get(val);
            int last = array.size() - 1;
            int lastVal = array.get(last);
            array.set(pos, lastVal);
            array.remove(last);
            map.put(lastVal, pos);
            map.remove(val);
            return true;
        }

        /**
         * Get a random element from the set.
         */
        public int getRandom() {
            return array.get(randomor.nextInt(array.size()));
        }
    }

    public static void main(String[] args) {
        RandomizedSet obj = new RandomizedSet();
        obj.insert(1);
        obj.insert(2);
        obj.insert(3);
        obj.insert(4);
        obj.remove(2);
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
        System.out.println(obj.getRandom());
    }
}
